package com.wss.lsl.test.driven.arithmetic.heap;

import java.math.BigDecimal;


/**
 * 堆demo
 * 
 * @author sean
 *
 */
public class HeapDemo {

	private int[] heap;

	public HeapDemo(int[] heap) {
		super();
		this.heap = heap;
	}

	/**
	 * 向上移元素算法
	 * 
	 * @param n
	 */
	public void siftup(int n) {
		int p;
		while (true) {
			if (n == 1) {
				// 没有父节点了
				break;
			}
			p = n / 2;// 父节点位置
			if (heap[p] <= heap[n]) {
				// 已经满足堆的条件，结束
				break;
			}
			// 父节点比子节点大，交换位置
			swap(n, p);

			n = p;
		}
	}

	/**
	 * 向下移动元素算法.
	 * <p>
	 * 设置第一个元素的值，然后向下调整堆
	 * </p>
	 * 
	 * @param n
	 */
	public void siftdown(int element) {

		heap[1] = element;
		int n = heap.length - 1;
		int c, i = 1;
		while (true) {
			c = i * 2;
			if (c > n) {
				// 没有子节点了，结束
				break;
			}

			if (c + 1 <= n) {
				// 存在右节点，取其中较小的
				if (heap[c + 1] < heap[c]) {
					c++;
				}
			}

			if (heap[i] <= heap[c]) {
				// 满足堆的条件，结束
				break;
			} else {
			}
			// 子节点比父节点小，交换
			swap(c, i);

			i = c;
		}
	}

	/**
	 * 校验堆
	 */
	public void verify() {

		for (int i = 1; i < heap.length; i++) {
			verify(i, 2 * i);
			verify(i, 2 * i + 1);
		}
	}

	private void verify(int p, int c) {
		if (c < heap.length) {
			if (heap[p] > heap[c]) {
				throw new RuntimeException("无效的堆");
			}
		}
	}

	/**
	 * 交换两个元素的位置
	 * 
	 * @param i
	 * @param j
	 */
	private void swap(int i, int j) {
		if (i == j) {
			return;
		}

		int temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;
	}

	/**
	 * 按格式打印堆
	 */
	public void report() {
		int length = heap.length - 1;
		double deep2 = Math.log(length - 1) / Math.log(2);
		int deep = (int) (new BigDecimal(deep2)
				.setScale(0, BigDecimal.ROUND_UP).doubleValue());

		int count = 0;
		int index = 0;
		for (int i = 1; i <= length;) {
			for (int d = 0; d < (deep - index - 1); d++) {
				if (d == (deep - index - 1) - 1) {
					for (int temp = 0; temp < 4; temp++) {
						System.out.print(" ");
					}
				} else {
					for (int temp = 0; temp < 5; temp++) {
						System.out.print(" ");
					}
				}
			}
			for (int j = 0; j < Math.pow(2, index) && (j + i) <= length; j++) {
				System.out.print(String.format("%5d", heap[i + j]));
				count++;
				if ((j + 1) % 2 != 0) {
					for (int temp = 0; temp < 4; temp++) {
						System.out.print(" ");
					}
				}
			}
			System.out.println();
			System.out.println();

			i += Math.pow(2, index);
			index++;
		}

		System.out.println(String.format("%5d%5d", length, count));
	}

}
